home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1996 #15 / Monster Media Number 15 (Monster Media)(July 1996).ISO / prog_c / cuj0696.zip / DWYER.ZIP / POKER.TST / README.PKR < prev    next >
Text File  |  1996-01-04  |  9KB  |  233 lines
  1.  
  2. DESCRIPTION OF THE POKER TEST
  3.  
  4. Introduction
  5. ------------
  6.  
  7. This test is also called the partition test.  In a classical
  8. Poker test, N groups of five successive integers are examined
  9. for one of the following seven patterns [K1, p. 62]::
  10.  
  11.         All different:  abcde
  12.              One pair:  aabcd
  13.             Two pairs:  aabbc
  14.       Three of a kind:  aaabc
  15.            Full house:  aaabb
  16.        Four of a kind:  aaaab
  17.        Five of a kind:  aaaaa
  18.  
  19.  
  20. In our implementation, N groups of k successive random integers
  21. are examined. Instead of counting the occurrence of the patterns
  22. shown above, we count the number of _distinct_ values in each set
  23. of k numbers.  For example, when k = 5 we search for one of the
  24. following five patterns:
  25.  
  26.         5 different = all different
  27.         4 different = one pair
  28.         3 different = two pairs, or three of a kind
  29.         2 different = full house, or four of a kind
  30.         1 different = five of a kind
  31.  
  32. One can imagine Hoyle whirring in his grave [M1].
  33.  
  34. This test is easier to implement than the classical Poker test
  35. and Knuth [K1, p. 62] suggests that it is almost as good.  The
  36. classical Poker test uses groups more closely related to the
  37. card game, but this test is both easier to implement and more
  38. flexible because the number of elements in a pattern can range
  39. from four to eight.  When k = 6, for example, the search is on
  40. one of six patterns:
  41.  
  42.         6 different = all different
  43.         5 different = one pair
  44.         4 different = two pairs, or three of a kind
  45.         3 different = full house, four of a kind, or three pair
  46.     2 different = two of three of a kind, five of a kind,
  47.               or four of a kind and a pair
  48.         1 different = six of a kind
  49.  
  50. The code fragment that performs this test in shown in listing1.pkr.
  51. The idea is to start by assuming that all cards are different.  When
  52. two cards are matched, the number different is decremented by one.
  53. The search starts with the first card and the remaining cards in the
  54. deck are scanned.  Then the second card is matched with the remaining
  55. cards (those that follow) unless it has already been matched, etc.
  56. The outer loop (line 7) moves through the deck, one card at a time.
  57. If the card has not already been matched (line 9), the inner loop
  58. compares its value with those remaining (line 13).
  59.  
  60.  
  61. The probabilities associated with these patterns is calculated
  62. as follows:
  63.  
  64.     Let k be the number of elements in a pattern and r be
  65.     the number of different values.  Then, the probability
  66.     that there are r different values in the pattern is
  67.  
  68.                 d(d-1)...(d-r+1)                        | [r] is subscript r
  69.         p[r] =  ----------------{k,r}                   | ^k is exponent k
  70.                        d^k                              | {k,r} should be
  71.                                                         | large { with k & r
  72.                                                         | stacked like this:
  73.                                                         |    k
  74.                                                         |    r
  75.     where {k,r} is a Stirling number of the second kind.|
  76.  
  77. A Stirling number of the second kind, {k,r}, is the number of ways
  78. of partitioning k elements into r non-empty subsets ([H1], page 824).
  79.  
  80. The Poker test is implemented as program pokertst.  This program
  81. performs a Kolmogorov-Smirnov analysis on probabilities from 100
  82. chi-square tests.  The parameters that determine how the chi-square
  83. tests are performed are specified by the user.  These parameters
  84. are read from the console unless the input device is redirected.
  85. As usual, prompts and messages are written to stderr and results
  86. are written to stdout.
  87.  
  88. Running the Poker Test
  89. ----------------------
  90.  
  91. To start program gaptst, you can say simply
  92.  
  93.         pokertst
  94.  
  95. and you will be prompted for the required inputs.
  96.  
  97. Alternatively, you can say
  98.  
  99.         pokertst < [myfile.inp]
  100.  
  101. and the program will take its input data from myfile.inp.
  102.  
  103. Seven input parameters are required:
  104.  
  105.     1.  Seed for the random number generator (-1 = Time of day)
  106.  
  107.         If you do not specify -1, the value entered must be less
  108.         than 65536.
  109.  
  110.     2.  Specification of generator to be tested
  111.  
  112.         If you are working interactively, you will see a list
  113.         of the generators that can be selected.  You enter the
  114.         character that represents your generator.  If you enter
  115.         a character that is not in the list, the library rand()
  116.         function will be used.
  117.  
  118.     3.  Number of cards per hand to be dealt [4-8]
  119.  
  120.         You can select a number between 4 and 8.  If you enter a
  121.         number less than 4, 4 will be assigned.  In your entry is
  122.         greater than 8, 8 will be assigned.
  123.  
  124.     4.  Number of unique cards in random deck [10-128]
  125.  
  126.         The limits have been assigned based on experience.  Most
  127.         of the test runs were conducted using the number 10.  If
  128.         your entry is less than 10, 10 will be assigned.
  129.  
  130.     5.  Minimum cell expectation [5-10]
  131.  
  132.         A cell is the same thing as a category.  Enter the expected
  133.         number of events per category (also called a pattern in the
  134.         introduction).  The lower limit of five is Knuth's suggestion
  135.         for all these tests.  The upper limit of 10 is arbitrary and
  136.         you can change it by redefining MAX_CELL_XPCT in header file
  137.         pokrdefs.h.
  138.  
  139.     6.  Number of hands per run that should be dealt [xxx ...]
  140.  
  141.         The program makes 100 runs to calculate chi-square statistics.
  142.         The number that you enter here specifies the number of hands
  143.         that will be used to calculate chi-square.  The xxx shown in
  144.         brackets will be a number that guarantees that at least four
  145.         cards in a hand will be used.
  146.  
  147. Execution of the Algorithm
  148. --------------------------
  149.  
  150. Once the input parameters have been processed and run-control
  151. variables have been set, the program will execute 100 chi-square
  152. runs as dictated by the input:
  153.  
  154.     1.  The program deals the number of hands specified at input 6.
  155.         Each hand consists of the number of cards per hand that you
  156.         specified at step 3.  Each 'card' is created by calling the
  157.         generator that you specified at input 2.  The output of the
  158.         generator modulo the number that you specified at input 4 is
  159.         used as a 'card.'
  160.  
  161.     2.  When a complete hand is collected, its pattern is determined.
  162.         This pattern is one of the five possible as described in the
  163.         introduction.
  164.  
  165.     3.  The number different is used as an index and the corresponding
  166.         counter in an array is tallied.
  167.  
  168.     4.  A chi-square statistic is calculated for the array of tallies.
  169.  
  170.     5.  A probability for the chi-square statistic is calculated.
  171.  
  172.     6.  The probability is stored in an array.
  173.  
  174.     7.  A running account of the steps and the number of variates
  175.         generated lets you know that the program is executing.
  176.  
  177. When the 100 runs are complete, a Kolmogorov-Smirnov test is run on
  178. the array to obtain statistics Kn+ and Kn- and their corresponding
  179. probabilities.
  180.  
  181. Final printouts consist of the Kolmogorov-Smirnov statistics and
  182. probabilities and the number of random numbers generated during the
  183. test.
  184.  
  185. Figure.1p shows a sample input file should you elect to redirect the
  186. input.  Figure.2p shows what you can expect to see if you redirect the
  187. output during the run on the sample input shown in figure 1p.  Figure.3p
  188. shows what your screen should look like if you redirect stdout to a file.
  189.  
  190. Error Printouts
  191. ---------------
  192.  
  193.     o Not enough hands were specified
  194.  
  195.       "Of the 5 Possible Categories, 1 Has a Cell Expectation Less Than
  196.        the Number Requested (5) and Will be Lumped With Others."
  197.  
  198.       "For the Inputs That You Have Provided At Least 50000 Hands are Required
  199.        to Fill All Categories."
  200.  
  201. These printouts will occur if you do not enter a large enough number at
  202. input step 6 (above).  The number of cards per hand will be reduced until
  203. your cell expectation can be met with the number of hands that you wanted
  204. to be dealt.  The minimum number of cards per hand is four.
  205.  
  206. If the number that you specify at input step 6 is less that the number
  207. the appears in the prompt, you have committed a fatal error.  Here is
  208. a sample of what is printed:
  209.  
  210.         "At Least 4 Cards Per Hand Are Required.
  211.          Your Inputs Allow Only 3."
  212.  
  213.  
  214. Timing Estimates
  215. ----------------
  216.  
  217. The run shown in figure.1p required about 1.8 seconds on my
  218. Pentium 100.  Naturally, the time required depends on the
  219. generator (and the CPU).  For the data shown, the range of
  220. times is from 1.8 seconds for the MSC library function rand()
  221. to 8.8 seconds for the generator by Stephen L. Moshier.
  222. Both tests required exactly 1,000,000 random numbers.
  223.  
  224. REFERENCE
  225.  
  226. H1. Handbook of Mathematical Tables, ed. by M. Abramowitz
  227.     and I. A. Stegun (Washington, D.C.: U.S. Gov't Printing
  228.     Office, 1964).
  229. M1. Albert H. Morehead et al, The New Complete Hoyle Revised,
  230.     Doubleday, London (1981).  According to this book, Edmond
  231.     Hoyle (1672-1769) died at least 50 years before Poker was
  232.     invented.
  233.